package org.leetcode.easy.leetcode112;

import org.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Solution
{

    public boolean hasPathSum2(TreeNode node,int targetSum)
    {
        if (node==null) return false;

        Queue<TreeNode> queNode = new LinkedList<>();
        Queue<Integer> queVal = new LinkedList<>();

        queNode.offer(node);
        queVal.offer(node.val);

        while (!queNode.isEmpty())
        {
            TreeNode nowNode = queNode.poll();
            Integer tempSum = queVal.poll();

            if (nowNode.left==null && node.right==null)
            {
                if (tempSum==targetSum)
                {
                    return true;
                }
                continue;
            }

            if (nowNode.left!=null)
            {
                queNode.offer(nowNode.left);
                queVal.offer(tempSum+nowNode.left.val);
            }

            if (nowNode.right!=null)
            {
                queNode.offer(nowNode.right);
                queVal.offer(tempSum+nowNode.right.val);
            }
        }

        return false;
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {

        if (root==null) return false;

        Queue<TreeNode> queNode = new LinkedList<>();

        Queue<Integer> queVal = new LinkedList<>();

        queNode.offer(root);
        queVal.offer(root.val);

        while (!queNode.isEmpty())
        {
            TreeNode now = queNode.poll();
            int temp = queVal.poll();

            //叶子节点
            if (now.left==null && now.right==null)
            {
                if (targetSum ==temp)
                {
                    return true;
                }
                continue;
            }

            if (now.left!=null)
            {
                queNode.offer(now.left);
                queVal.offer(temp+now.left.val);
            }

            if (now.right!=null)
            {
                queNode.offer(now.right);
                queVal.offer(temp+now.right.val);
            }
        }

        return false;
    }


}
